package com.fanwei.construction;

import com.fanwei.construction.printer.BinaryTreeInfo;

import java.util.*;

/**
 * @author fanwei
 * @version 1.0.0
 * @ClassName BinarySearchTree.java
 * @Description 二叉树的查找
 * @createTime 2022年04月08日 11:03:00
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {

    private int size;
    //根节点
    private Node<E> root;
    //比较器
    private Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public int size(){
        return 0;
    }

    public void clear(){}

    public void add(E element){
        //判断element元素
        elementNotNullCheck(element);
        if (root ==null){
            root = new Node<>(element,null);
            size++;
            return;
        }
        //记录每个节点的父节点
        Node<E> parent = root;
        //添加的节点不是在第一个节点上，找到父节点
        Node<E> node = root;
        //这个是匹配插入的元素与节点比较值
        int result = 0;
        while (node!= null){ //嵌套之后便利二叉树
           result = compare(element,node.element);
           parent = node;
            if (result > 0){// root的值比element小，放在右侧
                node = node.right;
            }else if (result < 0){ // root的值比element大，放在左侧
                node = node.left;
            }else { //第3种情况：两个值相同，已有该值！退出循环
                break;
            }
        }

        //插入新的节点,并定位其数的父节点与子节点关系
        Node newNode = new Node(element,parent);
        if (result > 0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;

    }

    public void remove(E element){}

    public boolean contains(E element){
        return false;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 前序遍历 树结构
     */
    public void proOrderTraversal(){
        //todo -- 默认从根节点获取
        proOrderTraversal(root);
    }

    public void proOrderTraversal(Node<E> node){
        if (node == null)return;
        System.out.println(node.element);
        proOrderTraversal(node.left);
        proOrderTraversal(node.right);
    }

    /**
     * 中序遍历
     */
    public void inOrderTraversal(){
        //默认用根节点
        inOrderTraversal(root);
    }

    public void inOrderTraversal(Node<E> node){
        if (node == null)return;
        inOrderTraversal(node.left);
        System.out.println(node.element);
        inOrderTraversal(node.right);
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal(){
        //默认用根节点
        postorderTraversal(root);
    }

    public void postorderTraversal(Node<E> node){
        if (node == null)return;
        inOrderTraversal(node.right);
        inOrderTraversal(node.left);
        System.out.println(node.element);

    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(){
        if (root == null)return;
        LinkedList<Node<E>> nodes = new LinkedList<>();
        nodes.add(root);

        while (!nodes.isEmpty()){
            Node<E> node = nodes.removeFirst();
            System.out.println(node.element);
            if (node.left!= null){
                nodes.add(node.left);
            }

            if (node.right!= null){
                nodes.add(node.right);
            }
        }
    }

    /**
     * 比较逻辑实现
     * @desc 通过实现Comparable接口的方法去比较矮哦
     * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E e1,E e2){
        //todo--这里实现了初始化时候赋予的比较器的方法
        if (comparator != null){
            return comparator.compare(e1,e2);
        }
        //
        return ((Comparable<E>)e1).compareTo(e2);
    }

    //判断element是否为空，null抛出异常
    public void elementNotNullCheck(E element){
        if (element == null){
            throw new IllegalArgumentException("element must not null....");
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node<E>)node).element;
    }

    //由于保证二叉树的两边链表所以需要Node的链表来表示左右节点关系
    //属性：
    //    父节点
    //      |
    //    当前节点
    //     /  \
    //  左节点 右节点
    private static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        //构建节点需给当前节点赋值父节点、当前节点
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }
}
